package base.day08;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 描述：
 * costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花
 * 费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多
 * 做k个项目 m表示你初始的资金 说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
 *
 * @author hl
 * @version 1.0
 * @date 2020/11/1 15:25
 */
public class IPO {
    public static class Node {
        int profit;
        int capital;

        public Node(int profit, int capital) {
            this.profit = profit;
            this.capital = capital;
        }
    }

    /**
     * @param k       最多做k个项目
     * @param w       起始资金
     * @param profit  每个项目的利润
     * @param capital 每个项目的启动资金
     * @return 最后的资金的
     */
    public int findMaximizedCapital(int k, int w, int[] profit, int[] capital) {
        //小根堆，根据每个项目的启动资金的大小排列
        PriorityQueue<Node> minCost = new PriorityQueue<>(new MinCostCompare());
        //大根堆，根据每个项目的利润排列
        PriorityQueue<Node> maxProfit = new PriorityQueue<>(new MaxProfitCompare());

        for (int i = 0; i < profit.length; i++) {
            minCost.add(new Node(profit[i], capital[i]));
        }

        for (int i = 0; i < k; i++) {
            //每次看看是否可以从大根堆中解锁新的项目到小根堆中
            while (!minCost.isEmpty() && w >= minCost.peek().capital) {
                maxProfit.add(minCost.poll());
            }
            while (maxProfit.isEmpty()) {//如果小根堆为空了，说明已经没有可做的项目，提前返回
                return w;
            }
            w += maxProfit.poll().profit;
        }
        return w;

    }

    public static class MinCostCompare implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.capital - o2.capital;
        }
    }

    public static class MaxProfitCompare implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.profit - o2.profit;
        }
    }


}
